class Node {
    public int data;//默认值为0
    public Node next;//默认值为0

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class MyLinkedList {
    public Node head;//保存单链表的头部节点的引用  默认值为null

    //头插法（插入的数据会逆着输出）
    public void addFirst(int data) {
        Node node = new Node(data);//创建一个新的节点node
        if (this.head == null) {//第一次插入节点的情况
            this.head = node;
            return;
        }/**单链表的插入的时候，要先绑后面*/
        node.next = this.head;//将head的引用传给node的next
        this.head = node;//让head指向node的引用
        //注意不能写成this.head=this.node;因为note是具体方法中定义的局部变量，而this只能访问属性，方法，构造方法等。
    }

    //打印单链表
    public void display() {
        Node cur = this.head;
        while (cur != null) {//不能写成cur.next！=null，因为最后一个节点的data也要打印
            System.out.print(cur.data + "   ");
            cur = cur.next;
        }
        System.out.println();
    }

    //尾插法（插入的数据会顺序输出）
    public void addLast(int data) {
        Node node = new Node(data);
        if (this.head == null) {//第一次插入时
            this.head = node;
            return;
        }
        Node cur = this.head;
        while (cur.next != null) {//cur.next为空时说明找到尾节点
            cur = cur.next;
        }
        cur.next = node;
    }

    //得到单链表的长度
    public int size() {
        Node cur = this.head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //查找关键字key是否包含在单链表中
    public boolean contains(int key) {
        Node cur = this.head;
        while (cur != null) {
            if (cur.data == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //按索引插入
    //1.任意位置插入，第一个数据节点的下标为0
    //2.要往Index位置插入，则需要cur先走到Index-1的位置，然后node.next=cur.next;cur.next=node;
    public void addIndex(int index, int data) {
        Node node = new Node(data);
        if (index == 0) {//头插法
            addFirst(data);
            return;
        }
        if (index == this.size()) {//尾插法
            addLast(data);
        }
        //先要找到Index-1位置的节点的地址
        Node cur = searchIndex(index);
        //进行插入
        node.next = cur.next;
        cur.next = node;
    }

    private Node searchIndex(int index) {
        //1.对index的位置进行合法性检测
        if (index < 0 || index > this.size()) {
            throw new RuntimeException("index位置不合法！");
        }
        Node cur = this.head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }


    private Node searchPrev(int key) {//找要删除元素的前驱节点
        Node prev = this.head;
        while (prev.next != null) {
            if (prev.next.data == key) {
                return prev;
            } else {
                prev = prev.next;
            }
        }
        return null;
    }

    //删除第一次出现关键字key的节点
    public void remove(int key) {
        if (this.head == null) {//链表为空直接返回
            return;
        }
        if (this.head.data == key) {//头部节点的data就是对应的key
            this.head = this.head.next;
            return;
        }
        Node prev = searchPrev(key);//找到要删除节点的前驱
        if (prev == null) {
            System.out.println("没有这个元素！");
        } else {
            Node del = prev.next;//del为要删除的节点
            prev.next = del.next;
        }

    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        Node cur = this.head.next;//cur代表要删除的节点，位置在head的后继
        Node prev = this.head;//prev的位置在head位
        while (cur != null) {
            if (cur.data == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        if (this.head.data == key) {//最后判断头部节点是否满足
            this.head = this.head.next;
        }
    }

    //释放内存的
    public void clear() {
        this.head = null;
    }

    //反转链表
    public Node reverse() {
        Node cur = this.head;
        Node prev = null;//前驱节点
        Node newHead = null;//反转之后新的头部节点
        while (cur != null) {
            Node curNext = cur.next;//curNext是用来记录cur.next的，因为反转后无法通过cur.next访问下一个节点
            if (curNext == null) {
                newHead = cur;
            }
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return newHead;
    }

    public void displayNewHead(Node newhead) {//反转后的打印方法
        Node cur = newhead;
        while (cur != null) {//不能写成cur.next！=null，因为最后一个节点的data也要打印
            System.out.print(cur.data + "   ");
            cur = cur.next;
        }
        System.out.println();
    }

    public Node middleNode() {//返回中间结点
        Node fast = this.head;
        Node slow = this.head;
        while (fast != null && fast.next != null) {
            //不能将fast.next!=null写在fast!=null,如果fast为空那么fast.next就会空指针异常
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public Node FindKthToTail(int k) {//倒数第k个节点。思路：快慢指针，快指针走k-1步，然后快慢指针一起走
        Node fast = this.head;
        Node slow = this.head;
        Node cur = this.head;
        if (k <= 0) {
            return null;
        }
        while (k - 1 > 0) {
            if (fast.next != null) {
                fast = fast.next;
                k--;
            } else {
                System.out.println("没有这个节点");
                return null;
            }
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public Node partition(int x) {//按x值将链表分为两部分(大于x和小于x)，然后连起来，顺序不变
        Node bs = null;
        Node be = null;
        Node as = null;
        Node ae = null;
        Node cur = this.head;
        while (cur != null) {
            if (cur.data < x) {
                //第一次插入
                if (bs == null) {
                    bs = cur;
                    be = cur;
                }
                //非第一次插入
                else {
                    be.next = cur;
                    be = be.next;
                }
            } else {
                //第一次插入
                if (as == null) {
                    as = cur;
                    ae = cur;
                }
                //非第一次插入
                else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //1.判断bs是否为空，如果为空，返回as
        if (bs == null) {
            return as;
        }
        //2.如果bs不为空，进行拼接
        else {
            be.next = as;
            //3.如果as不为空，将ae的next置为空
            if (as != null) {
                ae.next = null;
            }
            return bs;
        }
    }

    //删除一个有序链表中重复的元素
    public Node deleteDuplication() {
        Node newHead = new Node(-1);//newHead是虚拟节点，data随意设置
        Node tmp = newHead;//tmp是用来连接上一个不重复元素与下一个不重复元素的节点
        Node cur = this.head;//cur是遍历用的
        while (cur != null) {
            if (cur.next != null && cur.data == cur.next.data) {//cur.next==null会空指针异常
                while (cur.next != null && cur.data == cur.next.data) {//cur.next==null会空指针异常
                    cur = cur.next;
                }
                cur = cur.next;//多做一步循环，跳过cur.next.data(cur.data==cur.next.data).
            } else {
                while (cur.next != null) {
                    tmp.next = cur;
                    tmp = tmp.next;
                    cur = cur.next;
                }
            }
        }
        tmp.next = null;//手动置空，尾巴的next为null
        return newHead.next;//走完遍历后，tmp位置发生变化，这时只能利用newHead来返回头部结点
    }

    //链表的回文结构
    public boolean palindrome() {
        if (this.head == null) {//头结点为空，肯定不是回文结构
            return false;
        }
        if (this.head.next == null) {//只有一个头结点，必然是回文结构
            return true;
        }
        //1.找到单链表的中间结点
        Node fast = this.head;
        Node slow = this.head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //2.反转后半部分链表
        Node cur = slow.next;
        while (cur != null) {
            Node curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //3.一边从头部遍历，一边从尾部遍历
        while (slow != this.head) {
            if (this.head.data != slow.data) {
                return false;
            }
            if (this.head.next == slow) {//这一步是用来判断节点为偶数时的情况
                return true;
            }

            {
                this.head = this.head.next;
                slow = slow.next;
            }
        }
        return true;
    }

    public void reorderList(Node head) {//eg:1>2>3>4>5-----》1>5>2>4>3
        if (head == null) {
            System.out.println("链表为空 ");
        } else {//快慢指针找到中间结点
            Node fast = head;
            Node slow = head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            Node cur = slow.next;//从中间结点位置开始反转链表
            Node tmp = slow;
            while (cur != null) {
                Node curNext = cur.next;
                cur.next = slow;
                slow = cur;
                cur = curNext;
            }
            tmp.next = null;//将链表从中间节点位置断开
            int flg = 1;
            Node tag = head;
            Node tmpNext = head.next;
            while (tag.next != null) {//依次遍历两个链表
                if (flg == 1){
                    tag.next = slow;
                    slow = slow.next;
                } else {
                    tag.next = tmpNext;
                    tmpNext = tmpNext.next;
                }
                tag = tag.next;
                flg *= -1;
            }
        }
    }

    public boolean hasCycle() {//判断是否有环
        Node fast = this.head;
        Node slow = this.head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    public Node decetCycle() {//判断是否有环，有环的话找到进入环的第一个节点
        Node fast = this.head;
        Node slow = this.head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                break;
            }
            if (fast==null||fast.next==null){
                return null;
            }
        }
        fast = this.head;
        while (fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
   return fast;
    }
}